package demo;

/**
 * 反转链表
 */
class Solution1 {
	public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode tmp = head.next;
		ListNode newHead = reverseList(head.next);
		tmp.next = head;
		head.next = null;
		return newHead;
	}

	public ListNode reverseList1(ListNode head) {
		ListNode pre = null;
		ListNode curr = head;
		while(curr != null) {
			ListNode tmp = curr.next;
			curr.next = pre;
			pre = curr;
			curr = tmp;
		}
		return pre;
	}
}

